package 动态规划;

import java.util.Arrays;

public class No322零钱兑换 {

    /**
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
     * 如果没有任何一种硬币组合能组成总金额，返回 -1。
     * 你可以认为每种硬币的数量是无限的。
     *
     * 示例 1：
     * 输入：coins = [1, 2, 5], amount = 11
     * 输出：3
     * 解释：11 = 5 + 5 + 1
     * 示例 2：
     * 输入：coins = [2], amount = 3
     * 输出：-1
     * 示例 3：
     * 输入：coins = [1], amount = 0
     * 输出：0
     * 示例 4：
     * 输入：coins = [1], amount = 1
     * 输出：1
     */

    /**
     * 用动态规划求解,找出小钱的最少次数
     * 假设 2,3,5
     * f(2)=1
     * f(3)=1
     * f(4)=2
     * f(5)=1
     * //+都是多一次
     * f(6)=min(f(4)+2,f(3)+3)
     * f(7)=min(f(2)+5,f(3)+2+2,f(4)+3,f(5)+2)
     */
    public int coinChange(int[] coins, int amount) {

        int[] dp=new int[amount+1];
        dp[0]=0;

        for (int i = 1; i <= amount; i++) {
            dp[i]=amount+1;//初始为一个不可能的最大值
            for (int coin : coins) {
                if (i >= coin) {
                    //当前金额大于硬币金额,可以兑换
                    dp[i] = Math.min(dp[i],dp[i - coin]+1);
                }
            }
        }
        //没有符合的情况就返回-1
        return dp[amount]==amount+1?-1:dp[amount];
    }

    /**
     * 求凑出0块钱的最少次数
     * f(0)=0;
     * f(1)=min(f(1-coins[0..i]))+1
     * f(2)=min(f(1-coins[0..i]))+1
     */
    public int coinChangeAgain(int[] coins, int amount){

        Arrays.sort(coins);
        int[] dp=new int[amount+1];
        dp[0]=0;

        for (int i = 1; i <= amount; i++) {
            int minCount=amount+1;//给amount+1就行了,不用Integer.MaxValue
            for (int coin : coins) {
                if(coin<=i){
                    //当前硬币可以凑
                    minCount=Math.min(dp[i-coin]+1,minCount);
                }else {
                    break;
                }
            }
            dp[i]=minCount;
        }

        return dp[amount]==(amount+1)?-1:dp[amount];
    }

    public static void main(String[] args) {
        No322零钱兑换 n=new No322零钱兑换();
        int[] arr={2};
        int result = n.coinChangeAgain(arr, 3);
        System.out.println(result);
    }

}